#-*- coding:utf-8 -*-
# 假设有4个门，一直猫咪藏在门后面
# 每一回合，你可以打开一个门检查猫咪是否在门后面
# 如果没有抓到猫咪，那么猫咪必须向邻近的门走动一格
# 问至少需要多少打开门的机会，你一定能够抓到藏在门后面的猫咪

# 解题思路：
# 先从比较小的门数，总结相关规律
# 假设有3个门
# 111
#@:1
# H: 011   人类检查第1个门
# C: 111   猫咪走动后可能有猫咪的地方
### 可以看出已经失败了，盘面又变成起始状态了
# 因为对称的原因，检查第3个门也是行不通的
#@:2
# H: 101   人类检查第2个门
# C: 010   则我们能确定猫咪在第2个门后面

# 假设有4个门
# 1111
#@:1
# H: 0111
# C: 1111
### 第一步检查第1,3个门是行不通的

#@:2
# H: 1011
# C: 0111
#--------
# H: 0011
# C: 0111
#--------
### 第二步检查第2个门是行不通的

#@:3
# H: 1011
# C: 0111
# H: 0101
# C: 1010
# H: 1000
# C: 0100

# 解题过程中发现遇到的情况和A*寻路很相似
# 存在一个基础的盘面值和一个最终的目的值
# 1、初始状态
# 2、人类操作一步，猫咪操作一步形成一系列新的盘面
# 3、然后在新的盘面中继续执行第2步，一直到找到答案

# 注意：
# 1、记录节点绑定关系的时候，要区分人类节点和猫咪节点，open_l要一直存的都是人类节点
# 2、查询最终的路径的是猫咪节点->人类节点->猫咪节点->人类节点...这个顺序进行查找


def catch_cat(cnt):
    doors = 2 ** cnt - 1
    open_l = []
    close_l = []
    human_path = {}
    cat_path = {}
    open_l.append(doors)
    cat_path[str(doors)] = {"p":None, "c":0}
    final = []
    
    loop = 1
    while(len(open_l) > 0):
        # print("#####:" + str(loop) + ":START")
        # print(open_l)
        # print(close_l)
        # 拿出猫咪走一步后的一个盘面
        c = open_l.pop(0)
        close_l.append(c)
        cost = cat_path[str(c)]["c"]

        # 拿出当前的盘面状况并标记出所有可能的操作
        new_l = []
        for i in xrange(0, cnt):
            if c & (1 << i) == 0:
                continue
            neighbor = c & ~(1 << i)
            if not neighbor in open_l and not neighbor in close_l:
                new_l.append(neighbor)
                if not human_path.has_key(str(neighbor)):
                    human_path[str(neighbor)] = {"p": c, "c":cost + 1}
                elif cost + 1 < human_path[str(neighbor)]["c"]:
                    human_path[str(neighbor)] = {"p": c, "c":cost + 1}

        # print("#####:" + str(loop) + ":NEWL")
        # print(new_l)

        # 根据刚刚标记的操作生成猫咪移动后的场面
        for i in xrange(0, len(new_l)):
            c = new_l[i]
            cost = human_path[str(c)]["c"]
            p = 0
            for x in xrange(0, cnt):
                if c & (1 << x) != 0:
                    if x - 1 >= 0:
                        p = p | (1 << x - 1)
                    if x + 1 < cnt:
                        p = p | (1 << x + 1)
            if not p in open_l and not p in close_l:
                open_l.append(p)
            if not cat_path.has_key(str(p)):
                cat_path[str(p)] = {"p": c, "c": cost + 1}
            elif cost + 1 < cat_path[str(p)]["c"]:
                cat_path[str(p)] = {"p": c, "c": cost + 1}

            if p != 0 and p & p - 1 == 0 and not p in final:
                final.append(p)

    # print("#####:FINAL")
    # print(final)
    # print(cat_path)
    # print(human_path)

    min_v = doors
    min_i = 0
    for i in xrange(0, len(final)):
        if cat_path[str(final[i])]["c"] < min_v:
            min_i = i
            min_v = cat_path[str(final[i])]["c"]

    path = []
    c = final[min_i]
    path.insert(0, c)
    while c != doors:
        h = cat_path[str(c)]["p"]
        c = human_path[str(h)]["p"]
        path.insert(0, h)
        path.insert(0, c)

    print("Cnt:" + str(len(path) // 2 + 1))
    print("S:" + bin(path[0])[2:].zfill(cnt))
    for x in xrange(1, len(path)):
        if x % 2 == 1:
            print("H:" + bin(path[x])[2:].zfill(cnt))
        else:
            print("C:" + bin(path[x])[2:].zfill(cnt))


catch_cat(7)

# 通过打印结果，发现结果的规律如下，假设有n个门
## 奇数按照
# 2,3,4, ... n - 1
# 2,3,4, ... n - 1
## 偶数按照
# 2,3,4, ... n - 1
# n - 1, ... 4,3,2
# 按照这个顺序开门一定能找到猫咪
# 所需要的最少次数是 (n - 2) + (n - 2) = 2n - 4


############################################################################################
# 查看其他人的解决方案比我的更简单
# 注意：最主要的是少了比较获取次数最少的过程
# 因为使用的广度优先遍历，每一次到达某一个场面，都是最短路径到达的，因而最终不需要取最小值
import Queue
class Solution:
    def __init__(self, doors, path = [], possible = set()):
        self.doors = doors
        self.path = path
        self.possible = possible

    def generate_next_step(self):
        if not self.possible:
            return None
        next_steps = []
        print(self.possible)
        for i in self.possible:
            path = self.path + [i]
            possible = set()
            for elem in self.possible:
                if elem != i:
                    if elem - 1 >= 1:
                        possible.add(elem - 1)
                    if elem + 1 <= self.doors:
                        possible.add(elem + 1)
            s = Solution(doors = self.doors, path = path, possible = possible)
            next_steps.append(s)
            print(possible)
        return next_steps

def find_cat(n):
    checked_combination = set()
    solution_queue = Queue.Queue()
    solution_queue.put(Solution(doors = n, path = [], possible = set(i for i in range(1, n + 1))))
    while(True):
        s = solution_queue.get()
        next_steps = s.generate_next_step()
        if next_steps is None:
            return s.path

        for n in next_steps:
            if tuple(n.possible) not in checked_combination:
                checked_combination.add(tuple(n.possible))
                solution_queue.put(n)

print(find_cat(7))


##########################################################################################
# 另外一个解题思路
# 猫咪每一次只能移动一步，也就是猫咪的位置一定是奇偶交替出现
# 这种解题思路是把奇偶交替这个隐藏条件使用上了
###7
# 假设猫咪在[2,4,6]
# 检查2，猫咪可能[3,5,7]
# 检查3，猫咪可能[4,6]
# 检查4，猫咪可能[5,7]
# 检查5，猫咪可能[6]
# 检查6，没有猫咪，则猫咪初始时一定在奇数位置上[1,3,5]，但是玩家操作了奇数步，所以当前猫咪可能在[2,4,6]上
# 则重复上面的步骤就能找到猫咪
###6
# 假设猫咪在[2,4,6]
# 检查2，猫咪可能[3,5]
# 检查3，猫咪可能[4,6]
# 检查4，猫咪可能[5]
# 检查5，没有猫咪，则猫咪可能在[1,3,5]，玩家操作了偶数步
### 如果检查1则猫咪可能在[2,4,6]上
### 如果检查5则猫咪可能在[2,4]上
# 检查5，猫咪可能[2,4]
# 检查4，猫咪可能[1,3]
# 检查3，猫咪可能[2]
# 检查2，抓到猫咪